package binarytree

// 该文件是Copilot自动生成的，比我写的代码更简洁。但是感觉不如我写的好理解。
// https://leetcode.cn/problems/binary-tree-preorder-traversal/description/
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

// PreorderTraversal 先序遍历二叉树
// 思路：
// 1. 定义一个切片，用于存储遍历的结果
// 2. 定义一个递归函数，传入当前节点和切片
// 3. 如果当前节点为空，直接返回
// 4. 将当前节点的值添加到切片中
// 5. 递归调用左子树
// 6. 递归调用右子树
// 7. 返回切片
func PreorderTraversal(root *TreeNode) []int {
	// 定义一个切片，用于存储遍历的结果
	result := []int{}
	// 定义一个递归函数，传入当前节点和切片
	var preorder func(node *TreeNode)
	preorder = func(node *TreeNode) {
		// 如果当前节点为空，直接返回
		if node == nil {
			return
		}
		// 将当前节点的值添加到切片中
		result = append(result, node.Val)
		// 递归调用左子树
		preorder(node.Left)
		// 递归调用右子树
		preorder(node.Right)
	}
	preorder(root)
	return result
}

// 后续遍历二叉树
// 思路：
// 1. 定义一个切片，用于存储遍历的结果
// 2. 定义一个递归函数，传入当前节点和切片
// 3. 如果当前节点为空，直接返回
// 4. 递归调用左子树
// 5. 递归调用右子树
// 6. 将当前节点的值添加到切片中
// 7. 返回切片
func PostorderTraversal(root *TreeNode) []int {
	// 定义一个切片，用于存储遍历的结果
	result := []int{}
	// 定义一个递归函数，传入当前节点和切片
	var postorder func(node *TreeNode)
	postorder = func(node *TreeNode) {
		// 如果当前节点为空，直接返回
		if node == nil {
			return
		}
		// 递归调用左子树
		postorder(node.Left)
		// 递归调用右子树
		postorder(node.Right)
		// 将当前节点的值添加到切片中
		result = append(result, node.Val)
	}
	postorder(root)
	return result
}

// 中序遍历二叉树
// 思路：
// 1. 定义一个切片，用于存储遍历的结果
// 2. 定义一个递归函数，传入当前节点和切片
// 3. 如果当前节点为空，直接返回
// 4. 递归调用左子树
// 5. 将当前节点的值添加到切片中
// 6. 递归调用右子树
// 7. 返回切片
func InorderTraversal(root *TreeNode) []int {
	// 定义一个切片，用于存储遍历的结果
	result := []int{}
	// 定义一个递归函数，传入当前节点和切片
	var inorder func(node *TreeNode)
	inorder = func(node *TreeNode) {
		// 如果当前节点为空，直接返回
		if node == nil {
			return
		}
		// 递归调用左子树
		inorder(node.Left)
		// 将当前节点的值添加到切片中
		result = append(result, node.Val)
		// 递归调用右子树
		inorder(node.Right)
	}
	inorder(root)
	return result
}

// 层序遍历二叉树
// 思路：
// 1. 定义一个切片，用于存储遍历的结果
// 2. 定义一个队列，用于存储当前节点
// 3. 将根节点添加到队列中
// 4. 当队列不为空时，循环执行以下操作
// 5. 从队列中取出一个节点
// 6. 将当前节点的值添加到切片中
// 7. 如果当前节点的左子树不为空，将左子树添加到队列中
// 8. 如果当前节点的右子树不为空，将右子树添加到队列中
// 9. 返回切片
func LevelOrderTraversal(root *TreeNode) [][]int {
	// 定义一个切片，用于存储遍历的结果
	result := [][]int{}
	// 定义一个队列，用于存储当前节点
	queue := []*TreeNode{}
	// 将根节点添加到队列中
	if root != nil {
		queue = append(queue, root)
	}
	// 当队列不为空时，循环执行以下操作
	for len(queue) > 0 {
		// 定义一个切片，用于存储当前层的节点值
		level := []int{}
		// 定义一个临时队列，用于存储下一层的节点
		nextQueue := []*TreeNode{}
		// 遍历当前层的节点
		for _, node := range queue {
			// 将当前节点的值添加到切片中
			level = append(level, node.Val)
			// 如果当前节点的左子树不为空，将左子树添加到队列中
			if node.Left != nil {
				nextQueue = append(nextQueue, node.Left)
			}
			// 如果当前节点的右子树不为空，将右子树添加到队列中
			if node.Right != nil {
				nextQueue = append(nextQueue, node.Right)
			}
		}
		// 将当前层的节点值添加到结果中
		result = append(result, level)
		// 更新队列为下一层的节点
		queue = nextQueue
	}
	return result
}

// 前序遍历二叉树 迭代法
// 思路：
// 1. 定义一个切片，用于存储遍历的结果
// 2. 定义一个栈，用于存储当前节点
// 3. 将根节点添加到栈中
// 4. 当栈不为空时，循环执行以下操作
// 5. 从栈中取出一个节点
// 6. 将当前节点的值添加到切片中
// 7. 如果当前节点的右子树不为空，将右子树添加到栈中
// 8. 如果当前节点的左子树不为空，将左子树添加到栈中
// 9. 返回切片
func PreorderTraversalIterative(root *TreeNode) []int {
	// 定义一个切片，用于存储遍历的结果
	result := []int{}
	// 定义一个栈，用于存储当前节点
	stack := []*TreeNode{}
	// 将根节点添加到栈中
	if root != nil {
		stack = append(stack, root)
	}
	// 当栈不为空时，循环执行以下操作
	for len(stack) > 0 {
		// 从栈中取出一个节点
		node := stack[len(stack)-1]
		stack = stack[:len(stack)-1]
		// 将当前节点的值添加到切片中
		result = append(result, node.Val)
		// 如果当前节点的右子树不为空，将右子树添加到栈中
		if node.Right != nil {
			stack = append(stack, node.Right)
		}
		// 如果当前节点的左子树不为空，将左子树添加到栈中
		if node.Left != nil {
			stack = append(stack, node.Left)
		}
	}
	return result
}

// 后序遍历二叉树 迭代法
// 思路：
// 1. 定义一个切片，用于存储遍历的结果
// 2. 定义一个栈，用于存储当前节点
// 3. 定义一个临时栈，用于存储当前节点
// 4. 将根节点添加到栈中
// 5. 当栈不为空时，循环执行以下操作
// 6. 从栈中取出一个节点
// 7. 将当前节点添加到临时栈中
// 8. 如果当前节点的左子树不为空，将左子树添加到栈中
// 9. 如果当前节点的右子树不为空，将右子树添加到栈中
// 10. 当栈不为空时，循环执行以下操作
// 11. 从栈中取出一个节点
// 12. 将当前节点的值添加到切片中
// 13. 返回切片
func PostorderTraversalIterative(root *TreeNode) []int {
	// 定义一个切片，用于存储遍历的结果
	result := []int{}
	// 定义一个栈，用于存储当前节点
	stack := []*TreeNode{}
	// 定义一个临时栈，用于存储当前节点
	tempStack := []*TreeNode{}
	// 将根节点添加到栈中
	if root != nil {
		stack = append(stack, root)
	}
	// 当栈不为空时，循环执行以下操作
	for len(stack) > 0 {
		// 从栈中取出一个节点
		node := stack[len(stack)-1]
		stack = stack[:len(stack)-1]
		// 将当前节点添加到临时栈中
		tempStack = append(tempStack, node)
		// 如果当前节点的左子树不为空，将左子树添加到栈中
		if node.Left != nil {
			stack = append(stack, node.Left)
		}
		// 如果当前节点的右子树不为空，将右子树添加到栈中
		if node.Right != nil {
			stack = append(stack, node.Right)
		}
	}
	// 当临时栈不为空时，循环执行以下操作
	for len(tempStack) > 0 {
		// 从临时栈中取出一个节点
		node := tempStack[len(tempStack)-1]
		tempStack = tempStack[:len(tempStack)-1]
		// 将当前节点的值添加到切片中
		result = append(result, node.Val)
	}
	return result
}

// 中序遍历二叉树 迭代法
// 该方法是copilot生成的，在iteratetraversal.go中有lcj自己生成的代码，有一点思路上的不同!!!
// 思路：
// 1. 定义一个切片，用于存储遍历的结果
// 2. 定义一个栈，用于存储当前节点
// 3. 定义一个临时节点，用于存储当前节点
// 4. 将根节点添加到栈中
// 5. 当栈不为空时，循环执行以下操作
// 6. 如果当前节点不为空，将当前节点添加到栈中
// 7. 如果当前节点的左子树不为空，将左子树添加到栈中
// 8. 如果当前节点为空，从栈中取出一个节点
// 9. 将当前节点的值添加到切片中
// 10. 将当前节点的右子树添加到栈中
// 11. 返回切片
func InorderTraversalIterative(root *TreeNode) []int {
	// 定义一个切片，用于存储遍历的结果
	result := []int{}
	// 定义一个栈，用于存储当前节点
	stack := []*TreeNode{}
	// 定义一个临时节点，用于存储当前节点
	node := root
	// 当栈不为空时，循环执行以下操作
	for len(stack) > 0 || node != nil {
		// 如果当前节点不为空，将当前节点添加到栈中
		if node != nil {
			stack = append(stack, node)
			// 如果当前节点的左子树不为空，将左子树添加到栈中
			node = node.Left
		} else {
			// 如果当前节点为空，从栈中取出一个节点
			node = stack[len(stack)-1]
			stack = stack[:len(stack)-1]
			// 将当前节点的值添加到切片中
			result = append(result, node.Val)
			// 将当前节点的右子树添加到栈中
			node = node.Right
		}
	}
	return result
}
